<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
The Extended CHR Implementation
</TITLE>
</HEAD>
<BODY >
<A HREF="libman050.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman042.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc97">8.9</A>&nbsp;&nbsp;The Extended <FONT COLOR=purple>CHR</FONT> Implementation</H2><UL>
<LI><A HREF="libman051.html#toc48">Invoking the extended CHR library</A>
<LI><A HREF="libman051.html#toc49">Syntactic Differences</A>
<LI><A HREF="libman051.html#toc50">Compiling</A>
<LI><A HREF="libman051.html#toc51">Semantics</A>
<LI><A HREF="libman051.html#toc52">Options and Built-In Predicates</A>
<LI><A HREF="libman051.html#toc53">Compiler generated predicates</A>
</UL>

<A NAME="newchr"></A>
A new, extended, <TT>chr</TT> library has been developed, with the intention of providing
the basis for a system that will allow more optimisations than the previous 
implementation. At the same time, some of the syntax of the <FONT COLOR=purple>CHR</FONT>  has
been changed to conform better to standard Prolog. <BR>
<BR>
The system is still experimental, and provides no special support for 
debugging <FONT COLOR=purple>CHR</FONT>  code. Please report any problems encountered while 
using this system.<BR>
<BR>
The main user visible differences from the original <TT>chr</TT> library are as 
follows:
<UL CLASS="itemize"><LI CLASS="li-itemize">
The extended library produces code that generally runs about twice as fast
as the old non-debugging code. It is expected that further improvements
should be possible.
<LI CLASS="li-itemize"><FONT COLOR=purple>CHR</FONT>  code is no longer compiled with a special command &ndash; the normal
compile command will now recognise and compile <FONT COLOR=purple>CHR</FONT>  code when the extended
<TT>chr</TT> library is loaded. No intermediate Prolog file is produced. The
<TT>.chr</TT> extension is no longer supported implicitly.
<LI CLASS="li-itemize">Syntax of some operators have been changed to conform better to standard
Prolog.
<LI CLASS="li-itemize">A framework for supporting more than two head constraints has been
introduced. However, support for propagation rules with more than two heads
have not yet been added. Simplification and simpagation rules with more
than two heads are currently supported.
<LI CLASS="li-itemize">The compiler does not try to reorder the <FONT COLOR=purple>CHR</FONT>  any more. Instead, 
they are ordered in the way they are written by the user.
<LI CLASS="li-itemize"><TT>label_with</TT> is no longer supported. It can be replaced with
user defined labelling.
<LI CLASS="li-itemize">The operational semantics of rules have been clarified.
<LI CLASS="li-itemize">The <FONT COLOR=purple>CHR</FONT>  are run at the same priority before and after
suspensions. Priorities can be specified for <FONT COLOR=purple>CHR</FONT>  constraints.
<LI CLASS="li-itemize">There is no special support for debugging yet. The <FONT COLOR=purple>CHR</FONT>  code would be
seen by the debugger as the transformed Prolog code that is generated by
the compiler.
</UL>
<A NAME="toc48"></A>
<H3 CLASS="subsection"><A NAME="htoc98">8.9.1</A>&nbsp;&nbsp;Invoking the extended CHR library</H3>
The extended library is invoked by <CODE>lib(ech)</CODE>. Given that it is now
integrated into the compiler. It can be invoked from a file that contains
<FONT COLOR=purple>CHR</FONT>  code, as <CODE>:- lib(ech).</CODE>, as long as this occurs before the CHR
code.<BR>
<BR>
<A NAME="toc49"></A>
<H3 CLASS="subsection"><A NAME="htoc99">8.9.2</A>&nbsp;&nbsp;Syntactic Differences</H3>
As programs containing <FONT COLOR=purple>CHR</FONT>s are no longer compiled by a separate process, 
the <TT>.chr</TT> extension is no longer implicitly supported. Files with
the <TT>.chr</TT> extension can still be compiled by explicitly specifying 
the extension in the compile command, as in <TT>['file.chr']</TT>. Associated
with this change, there are some changes to the declarations of the <TT>.chr</TT>
format:
<UL CLASS="itemize"><LI CLASS="li-itemize">
<TT>operator/3</TT> does not exist. It is not needed because the
standard Prolog <TT>op/3</TT> declaration can now handle all operator 
declarations. Replace all <TT>operator/3</TT> with <TT>op/3</TT> declarations.
<LI CLASS="li-itemize">The other declarations <TT>handler constraints option</TT> are now handled
as normal Prolog declarations, i.e. they must be preceded with 
<TT>:-</TT>. This is to conform with standard Prolog syntax.
</UL>
The syntax for naming a rule has been changed, because the old method (using
<TT>@</TT> clashes with the use of <TT>@</TT> in modules. The new operator
for naming rules is <TT>::=</TT>. Here is part of the minmax handler in the
new syntax:
<PRE CLASS="verbatim">
:- handler minmax.
:- constraints leq/2, neq/2, minimum/3, maximum/3.
:- op(700, xfx, leq).

built_in    ::=  X leq Y &lt;=&gt; \+nonground(X), \+nonground(Y) | X @=&lt; Y.
reflexivity ::=  X leq X &lt;=&gt; true.
...
</PRE><A NAME="toc50"></A>
<H3 CLASS="subsection"><A NAME="htoc100">8.9.3</A>&nbsp;&nbsp;Compiling</H3>
After loading the extended <TT>chr</TT> library, programs containing <FONT COLOR=purple>CHR</FONT>  code can
be compiled directly. Thus, <FONT COLOR=purple>CHR</FONT>  code can be freely mixed with normal Prolog
code in any file. In particular, a compilation may now compile code from 
different files in different modules which may all contain <FONT COLOR=purple>CHR</FONT>  codes. This
was a problem with the old library because <FONT COLOR=purple>CHR</FONT>  code had to be compile
separately. <BR>
<BR>
In the extended library, <FONT COLOR=purple>CHR</FONT>  code can occur anywhere in a particular module, and
for each module, all the <FONT COLOR=purple>CHR</FONT>  code (which may reside in different files)
will all be compiled into one unit (<TT>handler</TT> declarations are ignored
by the system, they are present for compatibility purposes only), with the
same constraint store. <FONT COLOR=purple>CHR</FONT>  code in different modules are entirely 
separate and independent from each other. <BR>
<BR>
In order to allow <FONT COLOR=purple>CHR</FONT>  code to occur anywhere inside a module, and also 
because it is difficult to define a meaning for replacing multi-heads rules,
compilation of <FONT COLOR=purple>CHR</FONT>  code is always incremental when a new file for a
module is compiled, i.e. any existing <FONT COLOR=purple>CHR</FONT> 
code in a module is not replaced by those in the newly compiled
file. However, when the whole module is recompiled (i.e. compiling a file
with the <CODE>module/1</CODE> directive), or if the module is erased, then any 
existing CHR code in the module is erased along with the other code in the 
module.<BR>
<BR>
It is possible to clear out old <FONT COLOR=purple>CHR</FONT>  code in all modules when compiling a 
file. This is done
with the <TT>chr/1</TT> predicate. This first remove any existing <FONT COLOR=purple>CHR</FONT>  code in
any module before the compilation starts. It thus approximates the semantics
of <TT>chr/1</TT> of the old library, but no Prolog file is generated. It is
mainly intended for compatibility with the old library, and when you are
using CHR without using the module facilities.<BR>
<BR>
<A NAME="toc51"></A>
<H3 CLASS="subsection"><A NAME="htoc101">8.9.4</A>&nbsp;&nbsp;Semantics</H3>

<H4 CLASS="subsubsection">Addition and removal of constraints</H4>
In the old <TT>chr</TT> library, it was not clearly defined when a constraint
will be added to or removed from the constraint store during the execution of 
a rule.
In the extended <TT>chr</TT> library, all head constraints
that occur in the head of a rule are mutually exclusive, i.e. they cannot
refer to the same constraint. This ensures that similar heads in a rule
will match different constraints in the constraint store.
Beyond this, the state of a constraint &ndash; if it 
is in the constraint store or not &ndash; that has been matched in the head 
is not defined during the execution of the rest of the head and guard.
As soon as the guard is satisfied, any constraints removed by a rule will
no longer be in the constraint store, and any constraint that is not
removed by the rule will be present in the constraint store.<BR>
<BR>
This can have an effect on execution. For example, in the finite domain
example in the old <TT>chr</TT> directory (<TT>domain.chr</TT>), there is the following rule:
<PRE CLASS="verbatim">
 X lt Y, X::[A|L] &lt;=&gt; 
        \+nonground(Y), remove_higher(Y,[A|L],L1), remove(Y,L1,L2) |
        X::L2.
</PRE>
Unfortunately this rule is not sufficiently specified in the extended
<FONT COLOR=purple>CHR</FONT>, and can lead to looping under certain circumstances. The two <TT>remove</TT> predicate in the guard removes elements from the domain, but if no
elements are removed (because <CODE>X lt Y</CODE> is redundant, e.g. <CODE>X lt 5</CODE> with
<CODE>X::[1..2]</CODE>), then in the old <FONT COLOR=purple>CHR</FONT> execution, the body goal, the constraint
<CODE>X::L2</CODE> would not be actually executed, because the older constraint in
the head (the one that matched <CODE>X::[A|L]</CODE>) has not yet been removed when
the new constraint is imposed. With the extended <FONT COLOR=purple>CHR</FONT>, the old constraint
is removed after the guard, so the <CODE>X::L2</CODE> is executed, and this can
lead to looping. The rule should thus be written as:
<PRE CLASS="verbatim">
 X lt Y, X::[A|L] &lt;=&gt; 
        \+nonground(Y), remove_higher(Y,[A|L],L1), remove(Y,L1,L2),
                L2\==[A|L] |
        X::L2.
</PRE>

<H4 CLASS="subsubsection">Executing Propagation and simpagation rules</H4>
Consider the following propagation rule:
<PRE CLASS="verbatim">

p(X), q(Y) ==&gt; &lt;Body&gt;.

:- p(X).
</PRE>
The execution of this rule, started by calling <CODE>p(X)</CODE>, will try to match
all <CODE>q(Y)</CODE> in the constraint store, and thus it can be satisfied,
with <CODE>&lt;Body&gt;</CODE> executed,
multiple number of times with different <CODE>q(Y)</CODE>. <CODE>&lt;Body&gt;</CODE> for
a particular <CODE>q(Y)</CODE> will be executed first, before trying to match
the next <CODE>q(Y)</CODE>. The execution of <CODE>&lt;Body&gt;</CODE> may however cause the 
removal of <CODE>p(X)</CODE>. In this case, no further matching with <CODE>q(Y)</CODE>
will be performed.<BR>
<BR>
Note that there is no commitment with propagation and simpagation rule
if the constraint being matched is not removed:
<PRE CLASS="verbatim">
p(X), q(Y) ==&gt; &lt;Body1&gt;.
p(X), r(Y) ==&gt; &lt;Body2&gt;.

:- p(X).
</PRE>
Both rules will always be executed.<BR>
<BR>
The body of a rule is executed as soon as its guard succeeds. In the case
of propagation rules, this means that the other propagation rules for this
constraint will not be tried until the body goals have all been executed.
This is
unlike the old <FONT COLOR=purple>CHR</FONT>, where for propagation rules, the body is not executed
until all the propagation rules have been tried, and if more than one
propagation rule has fired (successful in its guard execution), then the
most recently fired rule's body is executed first. For properly written,
mutually exclusive propagation rule, this should not make a difference
(modulo the effect of the removal of constraints in the body).<BR>
<BR>

<H4 CLASS="subsubsection">Execution Priority</H4>
The priority at which an ECH rule is executed depends on the `active'
constraint, i.e. the constraint that triggered the execution of the
rules. Normally, the ECH rules are executed at the <I>default</I>
priority, but a different priority can be associated with a constraint when it
is declared, specifying the priority at which the ECH rules will be executed
when that constraint is the active constraint. 
<PRE CLASS="verbatim">
:- constraints chr_labeling/0:at_lower(1).
</PRE>
this specifies that if <TT>chr_labeling/0</TT> was the active constraint, then 
the rules will be executed at a lower priority than the default. The
priorities are mapped to the priority system of ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>, and <TT>at_lower(1)</TT> maps to a priority one lower than the default, so that ECH
rules executing at the default priority will execute first. This is
particularly useful for labelling, as this allow the other ECH constraints
to be executed during the labelling process rather than afterwards.<BR>
<BR>
The priority specified can be <TT>at_lower(N)</TT>, <TT>at_higher(N)</TT>, or
<TT>at_absolute_priority(N)</TT>. For <TT>at_lower(N)</TT>, the priority is the
default + N; for <TT>at_higher(N)</TT>, it is the default - N. <TT>at_absolute_priority(N)</TT> sets the priority to N, regardless of the default,
and its use is not recommended. The available priorities are from 1
(highest) to 11 (lowest). The default priority is initially set to 9, but
can be changed with the <TT>chr_priority</TT> option. Note that the priority
at which the rules will run at is determined at compile time, and changing
the default priority will only affect new constraints compiled after the
change. It should therefore only be used in a directive before any of the
ECH rules.<BR>
<BR>
This behaviour is different from the old <TT>chr</TT> library, and from older
versions of <TT>ech</TT> library, where the rules ran at different
priorities before and after suspension. This can lead to different
behaviours with the same rule, either with other constraints solvers, or
even with other CHR rules, as a woken CHR executes at much higher priority
than the initial run. With the current <TT>ech</TT> execution, the rules are
executed at the same priority before and after suspension, for the same
active constraint. The default priority is set at 9 so that it is very
likely to be lower than the priority used in other constraint solvers. The
user is now allowed to alter the priority of specific ECH constraints to
allow the user more control so that for example a labelling rule can run at
a lower priority than the other constraints.<BR>
<BR>
<A NAME="toc52"></A>
<H3 CLASS="subsection"><A NAME="htoc102">8.9.5</A>&nbsp;&nbsp;Options and Built-In Predicates</H3>
The <CODE>check_guard_bindings</CODE> and <CODE>already_in_store</CODE> options from
the old <TT>chr</TT> library are supported. Note that the extended compiler can
actually detect some cases where guard bindings cannot constrain any global
variables (for example, <CODE>var/1</CODE>), and will in such cases no check 
guard bindings.<BR>
<BR>
New options, intended to control the way the compiler tries to optimise
code, are introduced. These are intended for the developers of the compiler,
and will not be discussed in detail here. The only currently supported 
option in this category is <CODE>single_symmetric_simpagation</CODE>.<BR>
<BR>
Another new option, <CODE>default_chr_priority</CODE>, allows the default
priority to be changed, e.g.
<PRE CLASS="verbatim">
:- option(default_chr_priority, 6).
</PRE>
changes the default priority to 6, so the compiler would generate new CHR
code which defaults to this priority (unless overridden in the constraints
declaration). The available values are from 1 to 11.<BR>
<BR>
The old <FONT COLOR=purple>CHR</FONT>  built-ins, <CODE>chr_get_constraint/1</CODE> and
<CODE>chr_get_constraint/2</CODE> are both implemented in this library.<BR>
<BR>
A new built-in predicate, <CODE>in_chrstore/1</CODE>, is used to inspect the
constraint store:
<PRE CLASS="verbatim">
in_chrstore(+Constraint)
</PRE>
is used to test if <CODE>Constraint</CODE> is in the constraint store or not. It
can be used to prevent the addition of redundant constraints:
<PRE CLASS="verbatim">
X leq Y, Y leq Z ==&gt; \+in_chrstore(X leq Z)| X leq Z.
</PRE>
The above usage is only useful if the <CODE>already_in_store</CODE> option is
off. Note that as the state of a constraint that appears in the head is
not defined in the guard, it is strongly suggested that the user does not
perform this test in the guard for such constraints,<BR>
<BR>
<A NAME="toc53"></A>
<H3 CLASS="subsection"><A NAME="htoc103">8.9.6</A>&nbsp;&nbsp;Compiler generated predicates</H3>
A source to source transformation is performed on <FONT COLOR=purple>CHR</FONT>  code by the compiler,
and the resulting code is compiled in the same module as the <FONT COLOR=purple>CHR</FONT>  code. These
transformed predicates all begin with 'CHR', so the user should avoid using
such predicates. <BR>
<BR>
<A NAME="@default273"></A><BR>
<BR>
<HR>
<A HREF="libman050.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman042.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
